#include <bits/stdc++.h>

using namespace std;




struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution_I {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> ans;
        queue<TreeNode*> q;
        if(root==nullptr) return ans;
        q.push(root);
        while(!q.empty()){
            TreeNode* p=q.front();q.pop();
            ans.push_back(p->val);
            if(p->left) q.push(p->left);
            if(p->right) q.push(p->right);
        }
        return ans;
    }
};
//每一层一个vector
class Solution_II_1 {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int> > ans;
        queue<TreeNode*> q1,q2;
        if(root==nullptr) return ans;
        q1.push(root);
        vector<int> tmp;
        while(!q1.empty()||!q2.empty()){
            tmp.clear();
            while(!q1.empty()){
                TreeNode *p=q1.front();q1.pop();
                tmp.push_back(p->val);
                if(p->left) q2.push(p->left);
                if(p->right) q2.push(p->right);
            }
            if(tmp.size()>0) ans.push_back(tmp); tmp.clear();
            while(!q2.empty()){
                TreeNode *p=q2.front();q2.pop();
                tmp.push_back(p->val);
                if(p->left) q1.push(p->left);
                if(p->right) q1.push(p->right);
            }
            if(tmp.size()>0) ans.push_back(tmp);
        }
        return ans;
    }
};

//自定义一个入队列元素
struct level{
    int lev;
    TreeNode *node;
    level(int l,TreeNode *p):lev(l),node(p){};
};
class Solution_II_2 {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int> > res;
        queue<level*> q;
        if(root==nullptr) return res;
        int le=0;
        level *l=new level(le,root);
        q.push(l);
        vector<int> tmp;
        while(!q.empty()){
            level *p=q.front();q.pop();
            if(p->lev==le+1){
                res.push_back(tmp);
                tmp.clear();
                le++;
            }
            tmp.push_back(p->node->val);
            if(p->node->left){
                q.push(new level(le+1,p->node->left));
            }
             if(p->node->right){
                q.push(new level(le+1,p->node->right));
            }
        }     
        if(tmp.size()>0) res.push_back(tmp);   
        return res;
    }
};

//每一层一个vector
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int> > ans;
        stack<TreeNode*> q1,q2;
        if(root==nullptr) return ans;
        q1.push(root);
        vector<int> tmp;
        while(!q1.empty()||!q2.empty()){
            tmp.clear();
            while(!q1.empty()){
                TreeNode *p=q1.top();q1.pop();
                tmp.push_back(p->val);
                if(p->left) q2.push(p->left);
                if(p->right) q2.push(p->right);
            }
            if(tmp.size()>0) ans.push_back(tmp); tmp.clear();
            while(!q2.empty()){
                TreeNode *p=q2.top();q2.pop();
                tmp.push_back(p->val);
                if(p->right) q1.push(p->right);
                if(p->left) q1.push(p->left);
            }
            if(tmp.size()>0) ans.push_back(tmp);
        }
        return ans;
    }
};



int main(){




    return 0;
}